BOJ28353 고양이 카페

풀이

고양이의 무게를 오름차순으로 정렬해줍시다. 현재 남은 고양이들 중에 제일 가벼운 고양이와 “합쳐서 무게가 K이하”인것 중에서 제일 무거운 고양이를 매칭해주는것을 반복하면 되고, 이는 투포인터나 이분탐색등을 사용해서 구현할 수 있습니다. 정당성은 아래와 같이 보일 수 있습니다.

매 순간 제일 가벼운 고양이를 골라도 되는 이유

제일 가벼운 고양이를 안쓰고 최적해가 존재한다고 해봅시다. 해당 최적해의 아무 매칭이나 골라서 제일 가벼운 고양이로 바꿔줘도 여전히 제한을 만족하기 때문에 항상 제일 가벼운 고양이를 고르는 방식으로 답을 구할 수 있습니다.

매칭할때 “합쳐서 무게가 K이하”중 최대를 고르는 이유

매칭의 두 고양이 무게를 w[i]와 w[j]라고 합시다. 문제의 조건은 $w[i]+w[j]\leq{}K$이고, 제일 가벼운 고양이를 w[i]로 할 것이므로 매칭될 고양이의 무게는 K-w[i]이하입니다.(∵$w[j]\leq{}K-w[i]$) 매칭을 진행할 때마다 제일 가벼운 고양이 w[i]의 무게는 단조증가하므로 w[j]의 상한 K-w[i]는 단조감소합니다. 그렇기 때문에 상한이 클 때 최대한 큰거를 사용해둬야 나중에 불필요하게 버려지는 일이 없습니다. 더 확실한 증명은 최적매칭이 항상 ((((())))) 이러한 괄호쌍?양파?형태로 변형 가능하다는것을 보이면 되고, 그건 교차하는 두 매칭을 교차하지 않게 풀었을때 손해가 아님을 보이면 됩니다. 증명은 생략하겠습니다.